Search Results

Documents authored by Graf, Daniel

Document
DOI: 10.4230/LIPIcs.MFCS.2018.56
Collective Fast Delivery by Energy-Efficient Agents

Authors: Andreas Bärtschi, Daniel Graf, and Matús Mihalák

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
We consider k mobile agents initially located at distinct nodes of an undirected graph (on n nodes, with edge lengths). The agents have to deliver a single item from a given source node s to a given target node t. The agents can move along the edges of the graph, starting at time 0, with respect to the following: Each agent i has a weight omega_i that defines the rate of energy consumption while travelling a distance in the graph, and a velocity upsilon_i with which it can move. We are interested in schedules (operating the k agents) that result in a small delivery time T (time when the item arrives at t), and small total energy consumption E. Concretely, we ask for a schedule that: either (i) Minimizes T, (ii) Minimizes lexicographically (T,E) (prioritizing fast delivery), or (iii) Minimizes epsilon * T + (1-epsilon)* E, for a given epsilon in (0,1). We show that (i) is solvable in polynomial time, and show that (ii) is polynomial-time solvable for uniform velocities and solvable in time O(n+k log k) for arbitrary velocities on paths, but in general is NP-hard even on planar graphs. As a corollary of our hardness result, (iii) is NP-hard, too. We show that there is a 2-approximation algorithm for (iii) using a single agent.
Cite as

Andreas Bärtschi, Daniel Graf, and Matús Mihalák. Collective Fast Delivery by Energy-Efficient Agents. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 56:1-56:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bartschi_et_al:LIPIcs.MFCS.2018.56,
  author =	{B\"{a}rtschi, Andreas and Graf, Daniel and Mihal\'{a}k, Mat\'{u}s},
  title =	{{Collective Fast Delivery by Energy-Efficient Agents}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{56:1--56:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.56},
  URN =		{urn:nbn:de:0030-drops-96381},
  doi =		{10.4230/LIPIcs.MFCS.2018.56},
  annote =	{Keywords: delivery, mobile agents, time/energy optimization, complexity, algorithms}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.ICALP.2018.109
Brief Announcement: Hamming Distance Completeness and Sparse Matrix Multiplication

Authors: Daniel Graf, Karim Labib, and Przemyslaw Uznanski

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We show that a broad class of (+, diamond) vector products (for binary integer functions diamond) are equivalent under one-to-polylog reductions to the computation of the Hamming distance. Examples include: the dominance product, the threshold product and l_{2p+1} distances for constant p. Our results imply equivalence (up to poly log n factors) between complexity of computation of All Pairs: Hamming Distances, l_{2p+1} Distances, Dominance Products and Threshold Products. As a consequence, Yuster's (SODA'09) algorithm improves not only Matousek's (IPL'91), but also the results of Indyk, Lewenstein, Lipsky and Porat (ICALP'04) and Min, Kao and Zhu (COCOON'09). Furthermore, our reductions apply to the pattern matching setting, showing equivalence (up to poly log n factors) between pattern matching under Hamming Distance, l_{2p+1} Distance, Dominance Product and Threshold Product, with current best upperbounds due to results of Abrahamson (SICOMP'87), Amir and Farach (Ann. Math. Artif. Intell.'91), Atallah and Duket (IPL'11), Clifford, Clifford and Iliopoulous (CPM'05) and Amir, Lipsky, Porat and Umanski (CPM'05). The resulting algorithms for l_{2p+1} Pattern Matching and All Pairs l_{2p+1}, for 2p+1 = 3,5,7,... are new. Additionally, we show that the complexity of AllPairsHammingDistances (and thus of other aforementioned AllPairs- problems) is within poly log n from the time it takes to multiply matrices n x (n * d) and (n * d) x n, each with (n * d) non-zero entries. This means that the current upperbounds by Yuster (SODA'09) cannot be improved without improving the sparse matrix multiplication algorithm by Yuster and Zwick (ACM TALG'05) and vice versa.
Cite as

Daniel Graf, Karim Labib, and Przemyslaw Uznanski. Brief Announcement: Hamming Distance Completeness and Sparse Matrix Multiplication. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 109:1-109:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{graf_et_al:LIPIcs.ICALP.2018.109,
  author =	{Graf, Daniel and Labib, Karim and Uznanski, Przemyslaw},
  title =	{{Brief Announcement: Hamming Distance Completeness and Sparse Matrix Multiplication}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{109:1--109:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.109},
  URN =		{urn:nbn:de:0030-drops-91134},
  doi =		{10.4230/LIPIcs.ICALP.2018.109},
  annote =	{Keywords: fine-grained complexity, matrix multiplication, high dimensional geometry, pattern matching}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2017.2
Truthful Mechanisms for Delivery with Agents

Authors: Andreas Bärtschi, Daniel Graf, and Paolo Penna

Published in: OASIcs, Volume 59, 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)

Abstract
We study the game-theoretic task of selecting mobile agents to deliver multiple items on a network. An instance is given by $m$ packages (physical objects) which have to be transported between specified source-target pairs in an undirected graph, and $k$ mobile heterogeneous agents, each being able to transport one package at a time. Following a recent model [Baertschi et al. 2017], each agent i has a different rate of energy consumption per unit distance traveled, i.e., its weight. We are interested in optimizing or approximating the total energy consumption over all selected agents. Unlike previous research, we assume the weights to be private values known only to the respective agents. We present three different mechanisms which select, route and pay the agents in a truthful way that guarantees voluntary participation of the agents, while approximating the optimum energy consumption by a constant factor. To this end, we analyze a previous structural result and an approximation algorithm given in [Baertschi et al. 2017]. Finally, we show that for some instances in the case of a single package, the sum of the payments can be bounded in terms of the optimum.
Cite as

Andreas Bärtschi, Daniel Graf, and Paolo Penna. Truthful Mechanisms for Delivery with Agents. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 2:1-2:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bartschi_et_al:OASIcs.ATMOS.2017.2,
  author =	{B\"{a}rtschi, Andreas and Graf, Daniel and Penna, Paolo},
  title =	{{Truthful Mechanisms for Delivery with Agents}},
  booktitle =	{17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
  pages =	{2:1--2:17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-042-2},
  ISSN =	{2190-6807},
  year =	{2017},
  volume =	{59},
  editor =	{D'Angelo, Gianlorenzo and Dollevoet, Twan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.2},
  URN =		{urn:nbn:de:0030-drops-78891},
  doi =		{10.4230/OASIcs.ATMOS.2017.2},
  annote =	{Keywords: delivery, agent, energy optimization, approximation mechanism, frugality}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.74
All-Pairs 2-Reachability in O(n^w log n) Time

Authors: Loukas Georgiadis, Daniel Graf, Giuseppe F. Italiano, Nikos Parotsidis, and Przemyslaw Uznanski

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
In the 2-reachability problem we are given a directed graph G and we wish to determine if there are two (edge or vertex) disjoint paths from u to v, for given pair of vertices u and v. In this paper, we present an algorithm that computes 2-reachability information for all pairs of vertices in O(n^w log n) time, where n is the number of vertices and w is the matrix multiplication exponent. Hence, we show that the running time of all-pairs 2-reachability is only within a log factor of transitive closure. Moreover, our algorithm produces a witness (i.e., a separating edge or a separating vertex) for all pair of vertices where 2-reachability does not hold. By processing these witnesses, we can compute all the edge- and vertex-dominator trees of G in O(n^2) additional time, which in turn enables us to answer various connectivity queries in O(1) time. For instance, we can test in constant time if there is a path from u to v avoiding an edge e, for any pair of query vertices u and v, and any query edge e, or if there is a path from u to v avoiding a vertex w, for any query vertices u, v, and w.
Cite as

Loukas Georgiadis, Daniel Graf, Giuseppe F. Italiano, Nikos Parotsidis, and Przemyslaw Uznanski. All-Pairs 2-Reachability in O(n^w log n) Time. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 74:1-74:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{georgiadis_et_al:LIPIcs.ICALP.2017.74,
  author =	{Georgiadis, Loukas and Graf, Daniel and Italiano, Giuseppe F. and Parotsidis, Nikos and Uznanski, Przemyslaw},
  title =	{{All-Pairs 2-Reachability in O(n^w log n) Time}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{74:1--74:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.74},
  URN =		{urn:nbn:de:0030-drops-74510},
  doi =		{10.4230/LIPIcs.ICALP.2017.74},
  annote =	{Keywords: 2-reachability, All Dominator Trees, Directed Graphs, Boolean Matrix Multiplication}
}
Document
DOI: 10.4230/LIPIcs.STACS.2017.10
Energy-Efficient Delivery by Heterogeneous Mobile Agents

Authors: Andreas Bärtschi, Jérémie Chalopin, Shantanu Das, Yann Disser, Daniel Graf, Jan Hackfeld, and Paolo Penna

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
We consider the problem of delivering m messages between specified source-target pairs in an undirected graph, by k mobile agents initially located at distinct nodes of the graph. Each edge has a designated length and each agent consumes energy proportional to the distance it travels in the graph. We are interested in optimizing the total energy consumption for the team of agents. Unlike previous related work, we consider heterogeneous agents with different rates of energy consumption (weights w_i). To solve the delivery problem, agents face three major challenges: Collaboration (how to work together on each message), Planning (which route to take) and Coordination (how to assign agents to messages). We first show that the delivery problem can be 2-approximated without collaborating and that this is best possible, i.e., we show that the benefit of collaboration is 2 in general. We also show that the benefit of collaboration for a single message is 1 / log 2 which is approximately 1.44. Planning turns out to be NP-hard to approximate even for a single agent, but can be 2-approximated in polynomial time if agents have unit capacities and do not collaborate. We further show that coordination is NP-hard even for agents with unit capacity, but can be efficiently solved exactly if they additionally have uniform weights. Finally, we give a polynomial-time c-approximation for message delivery with unit capacities.
Cite as

Andreas Bärtschi, Jérémie Chalopin, Shantanu Das, Yann Disser, Daniel Graf, Jan Hackfeld, and Paolo Penna. Energy-Efficient Delivery by Heterogeneous Mobile Agents. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bartschi_et_al:LIPIcs.STACS.2017.10,
  author =	{B\"{a}rtschi, Andreas and Chalopin, J\'{e}r\'{e}mie and Das, Shantanu and Disser, Yann and Graf, Daniel and Hackfeld, Jan and Penna, Paolo},
  title =	{{Energy-Efficient Delivery by Heterogeneous Mobile Agents}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{10:1--10:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.10},
  URN =		{urn:nbn:de:0030-drops-70233},
  doi =		{10.4230/LIPIcs.STACS.2017.10},
  annote =	{Keywords: message delivery, mobile agents, energy optimization, approximation algorithms}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact